from itertools import product

matrix = [
        [6, 5, 0, 8, 7, 3, 0, 9, 0],
        [0, 0, 3, 2, 5, 0, 0, 0, 8],
        [9, 8, 0, 1, 0, 4, 3, 5, 7],
        [1, 0, 5, 0, 0, 0, 0, 0, 0],
        [4, 0, 0, 0, 0, 0, 0, 0, 2],
        [0, 0, 0, 0, 0, 0, 5, 0, 3],
        [5, 7, 8, 3, 0, 1, 0, 2, 6],
        [2, 0, 0, 0, 4, 8, 9, 0, 0],
        [0, 9, 0, 6, 2, 5, 0, 8, 1]]

# 输出结果
def printSudoku():
    global matrix
    for r in matrix:
        print('\t'.join(map(str, r)))

# 返回下一个未填的格子
def numberUnassigned() -> list[int]:
    global matrix
    try:
        return next([1, i, j] for i, j in product(range(9), range(9)) if matrix[i][j] == 0)
    except StopIteration:
        return [0, -1, -1]

# 检查是否能将值n填写在单元格[r][c]处
def isSafe(n: int, r: int, c: int) -> bool:
    # 检查所在行有无重复
    if any(matrix[r][i] == n for i in range(9)):
        return False

    # 检查所在列有无重复
    if any(matrix[i][c] == n for i in range(9)):
        return False

    # 检查所在九宫格
    row_start = (r // 3) * 3
    col_start = (c // 3) * 3
    if any(matrix[i][j] == n for i, j in product(range(row_start, row_start + 3), range(col_start, col_start + 3))):
        return False
    
    # 上述情况都没有，则说明可以填写n
    return True

# 使用回溯法解决数独问题
def solveSudoku() -> bool:
    global matrix
    a, row, col = numberUnassigned()
    if a == 0:
        return True

    # 尝试填写数字1-9到下一个未填写的格子
    for i in range(1, 10):
        if isSafe(i, row, col):
            matrix[row][col] = i

            # 通过递归执行DFS搜索
            if solveSudoku():
                return True
            
            # 还原状态
            matrix[row][col] = 0

    return False

if solveSudoku():
    printSudoku()
else:
    print('该数独问题无解!')
